SPOJ/SEQ - 339. Recursive Sequence/seq.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int mod = 1000000000;
  28
  29 struct Matrix {
  30     int size;
  31     vector< vector<int> > data;
  32     Matrix(int k) :size(k), data(k, vector<int>(k, 0)) { }
  33 };
  34
  35 Matrix operator * (const Matrix &a, const Matrix &b) {
  36     Matrix ans(a.size);
  37     for (int i = 0; i < a.size; ++i) {
  38         for (int j = 0; j < a.size; ++j) {
  39             for (int k = 0; k < a.size; ++k) {
  40                 ans.data[i][j] += (1LL * a.data[i][k] * b.data[k][j]) % mod;
  41                 ans.data[i][j] %= mod;
  42             }
  43         }
  44     }
  45     return ans;
  46 }
  47
  48 Matrix pow(const Matrix &m, int n) {
  49     if (n == 1) return m;
  50     if (n % 2 == 1) return m * pow(m, n - 1);
  51     Matrix half = pow(m, n / 2);
  52     return half * half;
  53 }
  54
  55 int main(){
  56     int C; cin >> C;
  57     while (C--) {
  58         int k; cin >> k;
  59         vector<int> b(k);
  60         for (int i = 0; i < k; ++i) cin >> b[i];
  61         Matrix m(k);
  62         for (int i = 0; i < k - 1; ++i) {
  63             m.data[i][i + 1] = 1;
  64         }
  65         for (int j = k - 1; j >= 0; --j) {
  66             cin >> m.data[k - 1][j];
  67         }
  68         int n; cin >> n;
  69         if (n > 1) m = pow(m, n - 1);
  70
  71         int ans = 0;
  72         for (int i = 0; i < k; ++i) {
  73             ans += (1LL * m.data[0][i] * b[i]) % mod;
  74             ans %= mod;
  75         }
  76         printf("%d\n", ans);
  77     }
  78     return 0;
  79 }